#include "DynamicArray.h"
#include <iostream>
#include<limits.h>

DynamicArray::DynamicArray(size_t capacity) : size(0), capacity(capacity)
{
    array = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray &a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
}

DynamicArray &DynamicArray::operator=(const DynamicArray &a)
{
    delete[] array;
    size = a.size;
    capacity = a.capacity;
    array = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
    return *this;
}

void DynamicArray::show()
{
    for (int i = 0; i < size; i++)
    {
        std::cout <<" "<< array[i] ;
    }
    std::cout << std::endl;
}

size_t DynamicArray::Size()
{
    return size;
}

void DynamicArray::ReSize(size_t capacity)
{
    this->capacity = capacity;
    this->size = (size > capacity) ? capacity : size;

    ElementType *newP = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        newP[i] = array[i];
    }
    delete[] array;
    array = newP;
}

void DynamicArray::InsertTail(const ElementType &element)
{
    if (size >= capacity)
    {
        ReSize(capacity + (capacity >> 1));
        // ReSize(2 * capacity );
    }
    array[size++] = element; // o(1)
}

//对于顺序表，尾插更方便
void DynamicArray::InsertHead(const ElementType &element)
{
    if (size >= capacity)
       ReSize(2*capacity);
    for (int i = size; i > 0; i--)   //o(n)
    {
        array[i] = array[i-1];
    }
    array[0] = element;
    size++;
}

//按值插入
void DynamicArray::InsertByIndex(int index, const ElementType &element)
{
    if (size >= capacity)
        ReSize(2*capacity);
        //非法位置排除
    if (index < 9 || index > size)
    {
        return;
    }
    for (size_t i = size; i > index; i--)   
    {
        array[i] = array[i-1];
    }
    array[index] = element;
    size++;
}

//按值查找
void DynamicArray::RemoveByIndex(int index)
{
    
    //非法位置排除
    if (index < 0 || index >= size)
    {
        return;
    }
    //扩容
    if (size >= capacity)
        ReSize(2*capacity);
    for (int i = index; i < size - 1; i++)  //o(n)
    {
        array[i] = array[i + 1];
    }
    size--;
}


//按位置查找
void DynamicArray::RemoveByElement(const ElementType& element)
{
    
    for (int i = 0; i < size; i++) //o(n^2)
    {
        if (array[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

ElementType DynamicArray::FindByElement(const ElementType &element)
{
    ElementType result;
    for (int i = 0; i < size; i++)    //o(n)
    {
        if (array[i] == element)
        {
            result.InsertTail(i);
        }
}
    return result;
}

void DynamicArray::UpdateByIndex(int index, const ElementType &element)
{
    if (index < 0 || index >= size)
        return;
        array[index] = element;   //o(1)
    
}

void DynamicArray::UpdateByElement(const ElementType &element, const ElementType &newValue)
{
    for (int i = 0;i< size; i++)
    {
        if (array[i] == element)
        {
            array[i] = newValue;
        }
    }
}

//插入排序
void DynamicArray::InsertSort(size_t start, size_t end)  
{
    for (size_t i =1; i < size; i++)
    {
        ElementType temp = array[i];
        size_t j= i - 1;
        while (j>= 0 && array[j] > temp)
        {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = temp;
    }
}

//去重算法
void DynamicArray::RemoveDuplicate()
{
     for (int i = 0; i < size; i++)
     {
        if(array[i]=array[i-1])
        {
            RemoveByIndex(i);
            i--;
        }
     }
}

//合并两个有序数列  (算法:归并排序) ->双指针
DynamicArray DynamicArray::Merge(const DynamicArray &a)
{
    int first = 0;
    int second = 0;
    DynamicArray result;
    while (first < size && second < a.size)  //都未到结尾
    {
        if (this->array[first] < a.array[second])
        {
            result.InsertTail(array[first]);
            first++;
        }
        else  //第二个比较小
        {
            result.InsertTail(a.array[second]);
            second++; //  a.array[secont++]
        }
    }
    while (first < this->size) //第一个未到结尾
    {
        result.InsertTail(array[first]);
        first++;
    }
    while (second < a.size) //第二个未到结尾
    {
        result.InsertTail(a.array[second]);
        second++;
    }
    return DynamicArray();
}

//找交集
DynamicArray DynamicArray::FindInSctn(const DynamicArray &a)
{
    DynamicArray result;
    // for (int i = 0; i < size; i++)
    // {
    //     for (int j = 0; j < a.size; j++)
    //     {
    //         if (array[i] == a.array[j])
    //         {
    //             result.InsertTail(array[i]);
    //         }
    //     }
    // }
    int first = 0;
    int second = 0;
    while (first < size && second < a.size)  //都未到结尾
    {
        if (this->array[first] == a.array[second])
        {
            result.InsertTail(array[first]);
            second++;
        }   
        else if (this->array[first] < a.array[second])
        {
            first++;
        }
        else
        {
            second++;
        }
    }
    return result;
}

//找并集 (只考虑有序情况)   ->双指针
DynamicArray DynamicArray::FindUnionSet(const DynamicArray &a)
{
    DynamicArray result = Merge(a);
    result.InsertSort(0, result.size - 1);
    int first = 0;
    int second = 0;
    while (first < size && second < a.size)  //都未到结尾
    {
        if (this->array[first] == a.array[second])
        {
            result.RemoveDuplicate();
            second++;
        }   
        else if (this->array[first] < a.array[second])
        {
            first++;
        }
}
    result.RemoveDuplicate();
    return result;
}

////找补集
DynamicArray DynamicArray::FindComplement(const DynamicArray &a)
{
    DynamicArray result;
    for (int i = 0; i < 100; i++)
    {
        if (FindByIndex(i) == nullptr)
        {
            result.InsertTail(i);
        }
    }
    for (int i = 0; i < a.size; i++)
    {
        if (a.FindByIndex(i) != nullptr)
        {
            result.RemoveByElement(a.array[i]);
        }
    }
    return result;
}

bool DynamicArray::operator==(const DynamicArray &a)
{
    if (size != a.size)
    {
        return false;
    }
    int first = 0;
    int second = 0;
    while (first < size && second < a.size)  
    {
        if (array[first] != a.array[second])
        {
            return false;
        }
        first++;
    }
    return true;
    // for (int i = 0; i < size; i++)
    // {
    //     if (array[i] != a.array[i])
    //     {
    //         return false;
    //     }
    // }
    // return true;
    //return this->FindDifference(a).size == 0;
}

size_t DynamicArray::BinarySearch(const ElementType &element)
{
    int left = 0;
    int right = size -1;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (array[mid] == element)
        {
            return mid;
        }
        else if (array[mid] <element)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return ULONG_MAX;
}

//判断子数列
bool DynamicArray::IsSubArray(const DynamicArray &a)
{
    for (int i = 0; i < size - a.size + 1; i++)
    {
        if (array[i] == a.array[0])
        {
            for (int j=0; j < a.size; j++)
            {
                
            }
        }
    }
    return false;
}

void DynamicArray::FastSort(size_t start, size_t end)
{
    if (start >= end)
    {
        return;
    }
    int left = start;
    int right = end;
    int temp = array[left];
    while (left<right)
    {
        while (left < right && array[right] >= temp)
        {
            right--;
        }
        if (left < right)          
        {
            array[left] = array[right];
        }
        while (left < right && array[left] <= temp)
             left++;
        if (left < right)
        {
            array[right] = array[left];
        }
    array[left] =temp;
    FastSort(start, left - 1); FastSort(left + 1, end);
    }
}

ElementType* DynamicArray::FindByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        return nullptr;
    }
    return &array[index]; //o(1)
}

//滑动窗口算法
bool DynamicArray::IsSubArray(const DynamicArray &a)
{
    for(int i = 0;i<=size - a.size;i++)
    {
        if (subsequence(i,a.size) == a)
        {
            return true;
        }
    }
    return false;
}



DynamicArray::~DynamicArray()
{
    delete[] array;
}